Example 1

Structure

Master Problem

• Objective: $ Min\ 2y $
• Constraint: $ y\geq0 $

Subproblem

• Objective: $Min\ 2x_1+3x_2$

• Constraints:

  $2x_1-x_2+3y\geq4$

  $x_1+2x_2+y\geq3$

  $y\geq0$

  $x_1\geq0,\ x_2\geq0$

Example 2

Structure

Master Problem

• Objective: $ Min\ 150x_1+230x_2+260x_3 $

• Constraints:

  $ x_1+x_2+x_3 \leq 500 $

  $x_1\geq0,\ x_2\geq0, \ x_3\geq0$

Subproblem 1

• Objective: $Min\ -\frac{1}{3}(170w_1-238y_1+150w_2-210y_2+36w_3+10w_4)$

• Constraints:

  $3x_1+y_1-w_1\geq200$

  $3.6x_2+y_2-w_2\geq 240$

  $w_3\leq6000$

  $w_1\geq0, \ w_2\geq0, \ w_3\geq0, \ w_4\geq0$

  $y_1\geq0, \ y_2\geq0$

  $x_1\geq0, \ x_2\geq0, \ x_3\geq0$

Subproblem 2

• Objective: $Min\ -\frac{1}{3}(170w_5-238y_3+150w_6-210y_4+36w_7+10w_8)$

• Constraints:

  $2.5x_1+y_3-w_5\geq200$

  $3x_2+y_4-w_6\geq240$

  $w_7+w_8\leq20x_3$

  $w_7\leq6000$

  $w_5\geq0, \ w_6\geq0, \ w_7\geq0, \ w_8\geq0$

  $y_3\geq0, \ y_4\geq0$

  $x_1\geq0, \ x_2\geq0, \ x_3\geq0$

Subproblem 3

• Objective: $Min\ -\frac{1}{3}(170w_9-238y_5+150w_10-210y_6+36w_11+10w_12)$

• Constraints:

  $2x_1+y_5-w_9\geq200$

  $2.4x_2+y_6-w_10\geq240$

  $w_11+w_12\leq16x_3$

  $w_11\leq6000$

  $w_9\geq0, \ w_10\geq0, \ w_11\geq0, \ w_12\geq0$

  $y_5\geq0, \ y_6\geq0$

  $x_1\geq0, \ x_2\geq0, \ x_3\geq0$

Example 3

Structure

Master Problem

• Objective: $ Min\ x_1+2x_2 $

• Constraints:

  $x_1\geq0, \ x_2\geq0 $

  $x_1+x_2\geq50$

Subproblem 1

• Objective: $Min\ 3y_1+4y_2$

• Constraints:

  $x_1+y_1\geq60$

  $x_2+y_2\geq70$

  $x_1\geq0,\ x_2\geq0$

  $y_1\geq0,\ y_2\geq0$

Subproblem 2

• Objective: $Min\ 5z_1+6z_2$

• Constraints:

  $y_1+z_1\geq80$

  $y_2+z_2\geq90$

  $y_1\geq0,\ y_2\geq0$

  $z_1\geq0,\ z_2\geq0$

Example 4

Structure

Master Problem

• Objective: $ Min\ 3x_1+2x_2 $

• Constraints:

  $x_1\geq0, \ x_2\geq0 $

  $x_1+x_2\geq27$

Subproblem 1

• Objective: $Min\ 4y_1+6y_2$

• Constraints:

  $x_1+y_2\geq34$

  $x_2+y_1\geq52$

  $x_1\geq0,\ x_2\geq0$

  $y_1\geq0,\ y_2\geq0$

Subproblem 2

• Objective: $Min\ 7z_1+8z_2$

• Constraints:

  $x_1+z_2\geq61$

  $x_2+z_1\geq29$

  $x_1\geq0,\ x_2\geq0$

  $z_1\geq0,\ z_2\geq0$

Subproblem 3

• Objective: $Min\ 10t_1+5t_2$

• Constraints:

  $x_1+t_2\geq43$

  $x_2+t_1\geq75$

  $x_1\geq0,\ x_2\geq0$

  $t_1\geq0,\ t_2\geq0$

Example 5

Structure

Master Problem

• Objective: $ Min\ x_1+2x_2 $

• Constraints:

  $x_1\geq0, \ x_2\geq0 $

  $x_1+x_2\geq50$

Subproblem 1

• Objective: $Min\ 3y_1+4y_2$

• Constraints:

  $x_1+y_1\geq60$

  $x_2+y_2\geq70$

  $x_1\geq0,\ x_2\geq0$

  $y_1\geq0,\ y_2\geq0$

Subproblem 2

• Objective: $Min\ 5z_1+6z_2$

• Constraints:

  $y_1+z_1\geq80$

  $y_2+z_2\geq90$

  $y_1\geq0,\ y_2\geq0$

  $z_1\geq0,\ z_2\geq0$

Subproblem 3

• Objective: $Min\ 0.5t_1+5t_2$

• Constraints:

  $x_1+t_2\geq43$

  $x_2+t_1\geq75$

  $x_1\geq0,\ x_2\geq0$

  $t_1\geq0,\ t_2\geq0$

Example 6

Structure

Master Problem

• Objective: $ Min\ 2y $
• Constraint: $ y\geq1 $

Subproblem

• Objective: $Min\ 2x_1+3x_2$

• Constraints:

  $x_1+2x_2+y\geq5$

  $y\geq0$

  $x_1\leq1,\ x_2\leq1$